package msb.class05;

import org.junit.Test;
import common.sort.AbstractSort;

/**
 * 归并排序
 * 非递归方法实现
 */
public class Code02_MergeSort2 extends AbstractSort {

    public void sort(int[] arr) {
        int step = 1;
        while (step <= arr.length) {
            int L = 0;
            int R = 0;
            int mid = 0;
            int group = 0;
            while (group * step * 2 <= arr.length) {
                L = group * step * 2;
                mid = Math.min(arr.length - 1, group * step * 2 + step - 1);
                R = Math.min(arr.length - 1, (group + 1) * step * 2 - 1);
                merge(arr, L, mid, R);
                group++;
            }
            step *= 2;
        }
    }


    //L..mid 与 mid+1..R进行归并
    public static void merge(int[] arr, int L, int mid, int R) {
        int leftPoint = L;
        int rightPoint = mid + 1;
        int[] tmpArr = new int[R - L + 1];
        int tmpPoint = 0;

        //左右指针越界，归并完整
        while (leftPoint <= mid || rightPoint <= R) {
            //左边指针越界，左边归并完毕，直接取右指针值
            if (leftPoint > mid) {
                tmpArr[tmpPoint++] = arr[rightPoint++];
                continue;
            }
            //右边指针越界，右边归并完毕，直接取左指针值
            if (rightPoint > R) {
                tmpArr[tmpPoint++] = arr[leftPoint++];
                continue;
            }

            //两边都没有越界，取最小值
            if (arr[leftPoint] <= arr[rightPoint]) {
                tmpArr[tmpPoint++] = arr[leftPoint++];
            } else {
                tmpArr[tmpPoint++] = arr[rightPoint++];
            }
        }

        for (int i = 0; i < tmpArr.length; i++) {
            arr[L + i] = tmpArr[i];
        }
    }

    @Test
    public void test() {
        Code02_MergeSort2 code01_mergeSort = new Code02_MergeSort2();
        code01_mergeSort.check();
    }
}
